package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhanghao
 * @create 2023-09-06 14:48
 * 三数之和
 * 先解决两数之和，定一寻二
 */
public class code15_3Sum {
    public static List<List<Integer>> threeSum(int[] nums){
        //有序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            //当前的位置不等于前面的那个位置的值，目的是排除重复的
            if(i == 0 || nums[i-1] != nums[i]){
                //这里使用两数之和解决问题
                List<List<Integer>> nexts = twoSum(nums,i + 1,-nums[i]);
                for (List<Integer> cur : nexts) {
                    cur.add(0,nums[i]);
                    ans.add(cur);
                }
            }
        }
        return ans;
    }

    /**
     * 找到从begin位置开始 nums中两个数字之和是target的集合
     * @param nums
     * @param begin
     * @param target
     * @return
     */
    private static List<List<Integer>> twoSum(int[] nums, int begin, int target) {
        int L = begin;
        int R = nums.length - 1;
        List<List<Integer>> ans = new ArrayList<>();
        while (L < R){
            if(nums[L] + nums[R] > target){
                R--;
            }else if(nums[L] + nums[R] < target){
                L++;
            }else {
                // nums[L] + nums[R] = target
                // 判断 L 位置的数字和 L - 1位置的数字是否相等.目的是为了防止最终的结果集有重复的
                if(L == begin  || nums[L - 1] != nums[L]){
                    List <Integer> list = new ArrayList<>();
                    list.add(nums[L]);
                    list.add(nums[R]);
                    ans.add(list);
                }
                L++;
            }
        }
        return ans;
    }
}
